package day_2022_7_to_8.day48;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


/**
 * @author haomin
 * @date 2022/08/05 15:24
 **/
public class Day21_1_Num623_AddOneRow {
    // 递归
    class Solution {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            // 递归出口
            if(depth == 0) return new TreeNode(val,null,root);
            if(depth == 1) return new TreeNode(val,root,null);

            if(root != null && depth > 1){
                root.left = addOneRow(root.left,val,depth-1==1?1:depth-1);
                root.right = addOneRow(root.right,val,depth-1==1?0:depth-1);
            }
            return root;
        }
    }
    // 层序遍历
    class Solution2 {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            if(depth == 1) return new TreeNode(val,root,null);

            Queue<TreeNode> queue = new LinkedList<>(); // 层序遍历用队列
            queue.offer(root);
            while(!queue.isEmpty()){
                if(--depth != 1){   // 1.深度未到depth 子树入队
                    int size = queue.size();
                    for(int i = 0;i < size;i++){
                        TreeNode cur = queue.poll();
                        if(cur.left != null)queue.offer(cur.left);
                        if(cur.right != null)queue.offer(cur.right);
                    }
                }else {             // 2.深度到达depth 改变子树结构
                    int size = queue.size();
                    for(int i = 0;i< size;i++){
                        TreeNode cur = queue.poll();
                        cur.left = new TreeNode(val,cur.left,null);
                        cur.right = new TreeNode(val,null,cur.right);
                    }
                }
            }
            return root;
        }
    }
}